The Ice Queen and the Wolf King
by BlueEyesBlueSkies
Summary: The story begins during the Battle of the Blackwater, and features an original female character who will eventually unite with Robb Stark. Robb will not die during the Red Wedding, and eventually they fight to save the North from those beyond the Wall. Timelines will shift and events will adjust as I bend the original plot to suit the story.
1. Chapter 1

**Hello! This is my first A Song of Ice and Fire/Game of Thrones fan fiction, so I welcome any and all feedback. I will unashamedly change timelines and plot around as it suits me to tell this story, so if that bothers you then this may not be the story for you. This idea came to me as I read some of the other amazing fictions posted, and after I ignored it for several days I just couldn't help but sit and start to write. I sincerely hope I do it justice. This tale will be filled with blood, gore, battles, angst, and romance. I hope you enjoy.**

 **Thank you for reading! Please drop a comment and let me know your thoughts. Any and all feedback are encouraged and welcome!** **J**

 **Necessary Disclaimer:**

 **I'm the author of this story. I did not create the world or any characters except for my original female character. Please do not sue me.**

Her eyes snapped open when the door to her cell was flung wide.

"King Joffrey requests your presence in the throne room." The raspy voice was unmistakable, and the resignation told her he'd drag her if he had to. He'd done it before, when she'd bothered to put up a fight.

Aching muscles and bones protested as she shifted carefully to sit, and then rise. Her eyes fluttered shut from the pain in her back and her thighs from the last beating, still fresh on her stinging skin, before she exhaled a long sigh. Chin raised high, she schooled her mask in place and opened her eyes once more as she turned towards the door.

Sandor Clegane couldn't hide the glimpse of respect and admiration glinting in his usually lifeless eyes as he watched her glide towards him, not a hitch in her step, not a crack in her calm, not a hint at the cuts and bruises gracing her pale skin under her finery.

"He's in a buggering mood today," he warned her, though he wasn't sure why he bothered. It wouldn't matter. She wouldn't say a word.

Head held high, she entered the throne room, grace rolling off her shoulders while blood dripped down her feet from yesterday's beating.

"Do you dare to dirty my floors with your blood," King Joffrey sneered from where he lounged on his golden throne with his golden crown atop his golden head.

She stood still as stone; gaze blank while he shot her a withering glare.

"You still dare defy me?" He snarled, crown sliding off its perfect golden perch to tilt over one ear. "Answer me!" He screamed, voice rising up an octave in his fury.

Not a muscle twitched, not an eye blinked, as she continued to stare blankly at the golden boy on his golden throne.

"I will beat you into submission," he snarled, face curling into another ugly sneer. "Ser Ilyn Payne! Teach this bitch what happens when you do not kneel or answer to your King!"

Sandor swallowed, careful to keep his face blank from where he lounged by the door. He knew what would happen to this little bird, same as he knew what would happen when his other little bird failed to please King Joffrey. His stomach rolled at the thought of another graceful back, beaten to a bloody pulp by one who had sworn to protect maidens fare. The little bird upstairs had scarcely left her cage since the last round, but lucky for her Joffrey's anger had shifted to the woman who refused to bend before him now.

The sharp crack of the flat of Ser Payne's broadsword meeting her bloodied flesh had Sandor swallowing back his bile. How this dog longed to bite the hand that fed him.

Several more smacks pierced the air, but still she did not break. Her graceful features stone in the face of his wrath, not a hint of pain flickering in those icy blue eyes. Her feet strong, her body sure as she withstood the blows of the boy king in front of her and the false knight behind her.

"Enough!" King Joffrey sneered, waving gold-covered hand as he rose from his golden throne and strolled haughtily up to the maiden before him. "Bend the knee before your King, whore!" He screamed, spittle flying to drip down her high cheeks.

"Show me a King worthy, and I may consider it."

The liquid honey in her voice belied the ice her tone conveyed, the musical tones dancing with strength while cutting like glass the boy king before her.

A golden fist raised in a flash, crashing upon a spit soaked cheek and slicing into the paleness until a single drop of blood trickled down to dance with the others pooling on the floor. "You dare to deny your King, bitch?" His highness squealed, raising his fist to land another blow. A second trickle joined the first, and matching cuts graced those sharpened cheeks.

King Joffrey blustered fussed, red staining golden cheeks as he whirled to stride back to his golden throne. "Take her away, and teach her a lesson, Hound!"

She turned, face once again the icy mask, body once again turned to stone, while the court watched blood rain down out of the slits in her back as she glided out of the throne room and back to her cell, the Hound behind her.

As the iron creaked open and she was returned to her rusted cage, Sandor entered behind her. "I warned you, little bird," he rasped, burnt face twitching at the savage display of flesh and fabric soaked through with blood on her back.

She shut her eyes briefly, swallowing as she sent a prayer to the Gods before turning back to send a frozen glare to the dog before her. "We haven't much time." Her voice dripped over him, chasing out the sadness as he saw the dullness sharpen to glass in her eyes.

He nodded, removing his cloak and pulling out the two dragonglass daggers he'd smuggled her from King Joffrey's armory. "Show me again," he rasped, eyes hard as he handed the blades by the hilt to her.

She crouched in the fighters stance he'd taught her, elegance and lethal combined as she whirled and twisted and turned, oblivious to the blood running down her back and the bruises swelling her pale blue eyes and cheeks. And as he dodged and parried and turned, he quickly felt the cool press of the blade slip through his best defenses to kiss his neck.

She withdrew, stepping back to breathe and thank the Gods. "You're ready," he confirmed, burnt side of his face twitching with pride.

"I am," she nodded in agreement, ice hard in her eyes as they held his own. "I'm ready to kill the golden King."

She lay on the cot in her cell, eyes closed as she watched her body arch and flip and twist around the boy King and his whore mother, slicing them to bits while the gold and blood curl and freeze to ice, forever locked in a sickening embrace for time to bear witness.

She prayed to the Gods they grant her mind strength, her body ice, her soul resolve as she did what needs be done. She thought of what Sansa Stark had whispered to her during one of their passings by the throne room, the Stark code. Winter was coming.

Cold air blew out of her nostrils, tendrils twisting and fading into the night. Sansa Stark was nearly correct. Winter wasn't coming. Winter was here.


	2. Chapter 2

She stood before the boy King in what was once finery but had long since been sliced to rags, crimson blood staining the golden carpets on his golden floor while he screeched and squawked from his golden throne. Stannis Baratheon's ships were spotted in the Blackwater, creeping closer, death blowing over the bay as the boy king blustered on the throne.

As he road out to meet his challenger, oblivious to the impending doom, she was returned to her cell with threat of death should the boy king lose his golden throne.

She was not afraid. Death and her had made a deal long ago, and it was not her time to die. There was too much left for her to do.

Fire lit the night sky out of her small window, piercing the darkness as the screams of men and beast echoed through the night. A figure appeared at the door of her cell, unlocking and throwing it wide. She saw the wild fear in the eyes of the Hound as he tossed her the blades they'd practiced with for so long.

"Time to fly, little bird," he rasped, body tense as he nodded for her to slip out of the cell.

As she slipped past him to steal down the stone corridor, she turned to see him headed away from her and further into the Keep. "And what of you?" She called softly.

He turned his head towards her, burnt skin glowing in the firelight. "This is not my night to deliver death. This is my night to protect life," he said softly.

She nodded, ice blue eyes flashing as she reached out a cold pale hand. "Thank you, Sandor. Thank you for everything. Keep Sansa safe."

His knarled hand reached out to strongly clasp her own. "Gods be with you, my lady," he said wrily, before turning to steal off into the night.

She walked with purpose, footsteps sure and slow as she made her way to the throne room where whore queen Cersei awaited her son with Ser Ilyn Payne. As she walked across the golden carpets up to the golden throne her resolve did not waiver. "Gods grant my body strength and my soul ice as I deliver death this night," she whispered, launching the first dagger to imbed itself between Ser Ilyn Payne's stunned eyes.

Women screamed, keened and cried as she strode up to the golden throne. The whore queen met her gaze with calm assurance as she pierced her dagger into her heart. "You will never kill my son," she choked out, gasping for breath as her lungs failed her.

She smiled, ice eyes sweeping the hall before returning to watch the life fade from the whore queen's eyes. "Your golden boy will no more sit the golden throne. I will pierce his heart, and bath in his blood in the bay as your court bathes in yours."

As suddenly as she had appeared she was gone, moving out of the Keep and into the night in search of the final death she'd pledged to deliver this night. The maidens left to wail and sob in the throne room bore witness to the ice in her eyes and the coldness in her heart as she left the whore queen to rain blood down the golden throne.

Walking through rains of fire, she slipped down to where the ships had docked to search for the golden boy who ruled the golden throne. Meeting his gaze in the distance, for the first time since she'd woken in the Red Keep, she smiled.

He was surrounded by white knights, cowering with fear as they fought for him to hold his throne, fought for him to survive this night. Later, some would call it witchcraft that led her to slip between his men until she was face to face with the final death she was to deal this night. "Guards! Save me!" He screamed, trembling as his fear dripped down his legs to stain the dirt below.

"Only death with save you now," she whispered into his ear as the dagger that had slain his mother pierced his heart.

The life drifted out of his eyes as he shuddered and twisted and slid down her body to fall to the ground at her feet, his blood sliding over her face and tattered dress to pool at her feet. "S-so cold," he stuttered, face paling as his golden eyes met her own and the golden crown slid to rest at her feet and splatter the crimson pool.

"Winter is here," she whispered, breath catching on the breeze as she turned to glide off into the night.

"They say the ships all froze in the harbor as King Renly came ashore to take the throne," the Greatjon boomed, reading from the latest scroll. "But when he entered the throne room, he found Ser Ilyn Payne and Cersei Lannister already dead, bodies frozen to ice while maidens were soaked in their blood."

King Robb tilted his head as he waited with baited breath. "And Sansa?" He asked, voice strong but filled with quiet hope.

"Alive!" The Greatjon roared, whooping with delight as a smile broke on King Robb's face. "King Joffrey was found dead as well, body crumpled in the dirt by the bay, frozen as well and lying in a puddle of blood and gold, according to this."

King Robb nodded, raising an eyebrow at the hesitant look on the Greatjon's face. "What else?"

His voice rumbled with awe and confusion as he read the remainder of the scroll to the man he'd declared his King. "They say," he hesitated, frowning before continuing. "They say, it was a _woman_ who dealt death that night."

Others snorted amusement as the Greatjon's face contorted with disbelief. "They say that as she delivered the final blow to the King, it was her who called forth the ice in the harbor to halt any escape, with her prayer to the Gods and promise to the people, before she disappeared into the night."

"And what did she say?" King Robb prompted, eyebrow raised at the tale.

"Winter is here."

A chill shot through the tent, laughter dying as they turned to their King with confusion. "Who is this woman?" He asked softly, face hard, eyes betraying no emotion.

The Greatjon shook his mighty head, dropping the scroll on the King's makeshift desk. "Nobody knows, it seems. She was drug into court by King Joffrey after one of his hunting expeditions, beaten and bloodied time and again for his amusement while he played court. It seems…" he hesitated once again, teeth catching his lip as he tilted his head.

"Do not stand on ceremony, Lord Umber," his King commanded firmly.

"They call her the Ice Queen, your Majesty."


	3. Chapter 3

_"Elyria," the voice echoed, piercing the blackness with a beam of light. She spun around, running towards the light while the cold snow dusted her face, burning her cheeks._

 _"Elyria," it called again, barely a whisper on a breeze. As she ran into the clearing, she saw the light emanating out from a singular Godswood tree, heart shaped face illuminated by the beam._

 _She approached, kneeling reverently at the roots and bowing her head. "Elyria," the tree spoke, branches coming down to cradle her like arms, sheltering her from the storm. "Your work is not yet finished."_

 _She raised her head, tears in her eyes as she scanned the face of the heart tree. "What needs doing, Gods? I am ever your faithful servant."_

 _The Gods smiled back in response, before the face of the tree faded and she was left staring at the vision of a boy, staring back at her._

 _"Elyria?" The boy asked, eyes closed as if in prayer._

 _"I'm here," she called softly, eyes wide as she watched the boy smile in response. "Who are you?"_

 _"You may call me Bran," the boy called softly, still refusing to open his eyes. "I see the Gods have answered my prayer."_

 _"You prayed for me?" She asked in bewilderment, confusion dripping off her words._

 _"I prayed for the one who would banish the lions from the Iron Throne. I prayed for the one who would vanquish Walder Frey, who would unite the North, who would lead us into battle to vanquish the whitewalkers."_

 _"I am the one who slayed the whore queen and the golden king," she confirmed, voice steady in the night. "I am the one who administered death and destruction that night, as King Renly claimed the Iron Throne."_

 _The boy smiled, eyes still pressed tightly shut, and nodded in response. "There's still more that needs doing, Elyria, and the Gods have chosen you to do it."_

 _She nodded, bowing her head to the will of the Gods. "Pray, give me guidance, Bran."_

 _Small hands reached out through the Godswood to press against her temples, raising her head. "Head North for The Twins. Amass an army of the common folk. You will know what needs doing." His voice was fading, words coming softer on the breeze as the face of the heart tree came back to the forefront._

 _"But how?" She called, uncertain in their will._

 _"Wait in the next tavern you come across until nightfall, Elyria. All will become clear." And as the Godswood branches returned, she collapsed into a heap on the cold snow._

Pulling her fur-trimmed cloak tighter around her chest, Elyria kept the hood pushed forward as her eyes scanned the tavern and its patrons. Sipping her ale from the corner, she nearly laughed at the ridiculousness of it. Despite her better judgment, here she found herself, sipping ale in the corner of a musty tavern, anxiously awaiting the arrival of some unknown person or persons, who would help her lead an army north to slay Walder Frey, and ultimately battle the white walkers.

It was insane.

But she'd never ignored the dreams the Gods sent her before, and despite the new appearance of Bran, she didn't intend to begin now. For whatever reason, the Gods had chosen her, and she would not make light of a calling of the Gods. So here she found herself, eyes sharp, ears open as she observed the comings and goings of the common folk in a small village on the road towards Harrenhal, and ultimately towards The Twins.

Darkness had long since fallen, and as the crowd turned raucous she feared she'd been mistaken, and perchance this was merely a dream and not a calling at all. Just as she prepared to signal the tavern keeper's wife to take her leave, the bell atop the door rang as two dusty travellers came in.

Bile rose to her throat as she took in the faces before her. The woman warrior was remarkable in itself, though no cause for alarm. But the man behind her, the stump of an arm bundled, that man allows for a shred of fear to slip into her heart.

The Kingslayer, Jaime Lannister himself.

She scoffed, downing the rest of her tankard of ale as she watched them make their way towards her corner to recline at a nearby table as the tavern keeper's wife brought them food and drink. These were the people Bran spoke of? This is who she was supposed to find?

Reclining back against the wall of the tavern, she pricked her ears to overhear their conversation.

"They're calling her the Ice Queen," the lady warrior scoffed, reaching across to gently stroke the edge of the stump.

The Kingslayer grunted, shifting in his seat as he shoveled stew into his mouth.

"Rumors suggested she was heading north, though beyond being a great beauty, reports differ as to her appearance."

The Kingslayer raised his head to nod in thought. "Even the ladies who'd watched her tortured couldn't agree, beyond confirming she was fair skinned, cold, and regal in composure."

The lady warrior nodded in agreement, swigging a drink from her tankard of ale. "We'll find her," she confirmed confidently, and he nodded his agreement.

"Aye, but it's once we find her that I'm not so certain of."

Elyria called out softly from her corner a few tables away. "Mayhaps she found you, Kingslayer."

Honeyed words whispered out through the darkness, bringing his head up with a sharp snap. Two sets of eyes stared at the hooded figure in the corner, before both rose simultaneously to bring themselves to close her in and sit across her. "I fear you have me at a disadvantage, my lady," he said smoothly, silky tones grating her nerves as she said a silent prayer to the Gods. "With whom do I have the pleasure of conversing with this night?"

Steeling her nerves, Elyria straightened from where she'd leaned, raising a gloved hand to push the hood back from her head. Her pale skin nearly translucent in the darkness while her ice blue eyes gazed at his, her voice did not tremble in her response. "Elyria Baratheon, daughter of Robert Baratheon and Minerva Tully, sister to Catelyn, Lysa and Edmure who died in childbirth." The Kingslayer's eyes widened with surprise as the lady warrior pursed her lips in thought.

"I had thought the girl dead in childbirth as well," he said with amusement, raising a brow as his eyes scanned her face noting the resemblance to her parentage. "And to what, pray tell, do we owe the pleasure of your company?"

Raising her chin, Elyria's eyes went cold. "Do you not know who sits before you, Kingslayer?" Her voice was hard and sharp.

He smirked, glancing at his lady warrior before tapping his fingers, a smile playing about his lips. "I fear I must not, my lady," he drawled, sarcasm dripping from his address.

"I am what you seek, Kingslayer. I am the one who slayed your sister and illicit son." His smile froze as his eyes hardened and the lady warrior stood swiftly to draw her sword.

"I am the one they call the Ice Queen."


	4. Chapter 4

**Thank you to those who have commented and are following this story! :) I really appreciate the comments- they help me gather my thoughts and push out this story! I hope you enjoy this chapter. Thank you!**

Elyria's eyes barely registered the sword before they flickered back to Jaime's before her. She blinked slowly at him as she watched his one fist curl and flex with frustration before he curtly jerked his head at Brienne, his eyes never leaving Elyria's. "Put the sword away, Brienne," he said curtly, face twisted with too many emotions to name.

"But, my lord-"

"Put it away!" He said harshly, slamming his fist down to rustle the wooden table. Brienne complied, shoving her sword back hastily and slamming down in her seat to glare at Elyria across the firelight.

"Where are you headed, Kingslayer?" She asked smoothly, face an expressionless mask. He scanned her features once more, noting the black curly hair pulled back in a long braid, the icy blue eyes, the graceful curve of her cheek and neck.

"I should ask the same of you, my lady," he ground out, eyes snapping in anger at the beauty before him.

Her eyes flicked around the tavern room, taking note of the dwindling number of travelers still left in their room, heavy into their cups and oblivious to the tension in the corner. She returned her gaze to his and arched an elegant eyebrow. Jaime snorted, rolling his eyes slightly before jutting out his chin. "Isn't it obvious, my lady? I was looking for you."

She nodded, a slight pull of her lips the only indication of the ghost of the smirk hovering there. "And I you, Kingslayer. But that is not what I asked. Where are you headed?"

Brienne scoffed, drawing a flick of Elyria's eyes. "It is no business of yours where we go once we finish with you."

Elyria gently inclined her head, the smirk coming to life, making the icy crystals in her eyes dance. "It appears, sir, you are a knight without a king then. Unless you intend to bend the knee to King Renly?"

Jaime frowned, firmly shaking his head. "Kneel before the man who slayed my father upon claiming the Iron Throne? I think not." He surveyed her face with a hint of interest, eyes lighting in spite of themselves. "Now that you know our purpose, or lack thereof, my lady, perhaps you'd share yours?"

Her face closed back in, all traces of the smirk and amusement disappearing as ice flashed in her eyes and her face became cold. "There are causes far greater than whose ass sits the Iron Throne. And there are more immediate threats to the realm that warrant your attention more thoroughly than vengeance. Would you agree, Kingslayer?"

Jaime's eyes narrowed, his brow creasing as he weighed her words shrewdly. "Speak plainly."

"The whitewalkers threaten beyond the Wall. And a few thousand men are all that stand between them and the whole of Westeros."

His expression dripped with skepticism as he searched her face, looking for the truth. "You've seen them? These terrors who roam the night, up beyond the wall?"

As she pressed her lips into a fine line, he shook his head with a scoff. "No, of course you haven't."

"They are real, Kingslayer. And the gods need your help to protect the realm."

His bark of laughter echoed in the emptying room, drawing a few started stares before travellers went back to their cups. "If these whitewalkers are as real as the North claim, a one armed knight wouldn't stand a chance, my lady. I think that is not enough motivation to sway me from my quest for vengeance, as you call it."

She gave a graceful turn of her head, releasing a pent-up sigh with a flutter of her eyes before they returned to once again study his face. "And who would you seek vengeance on first, Kingslayer? The one who slayed your sister and ill-begotten son, or the one who took your hand?"

His nostrils flared and his eyes blazed with fury, and Elyria saw Brienne's hand stray to the hilt of her sword as pain flashed over her face. "It seems then, ser," Elyria said sweetly, a grim smile stealing over her face, "we may be united in purpose."

Jaime lifted a brow as his eyes narrowed to slits. He tilted his head in interest as his fist clenched and released once more on top of the table. "And why, pray tell, would you have interest in avenging me, Ice Queen?"

Her smile at his use of the name the people had given her sent a chill racing through his spine, and he thought for not the first time that evening that the name was correct in more ways than one. "It seems Lord Walder Frey and Lord Bolton have joined to overthrow the Starks, Kingslayer. Greed makes many a man's honor falter when playing the game of thrones, and the Frey's and the Bolton's are not immune."

Anger and understanding dawned in his eyes as thoughts of splitting Locke from navel to nose danced in his mind's eye. He flicked his gaze quickly to Brienne, who nodded in agreement, before turning back to Elyria with a look of appreciation. "You would ask us to help King Stark keep his Northern throne, my lady?"

She smiled once more, shaking her head slightly, locks of black curls fluttering around her face. "I would ask you to help me save the realm, Kingslayer. Starting with avenging your hand and taking down Roose Bolton and Walder Frey once and for all."

Brienne snorted, pounding her fist on the table. "That is a distinction in words, but the results are the same, Lady Elyria," she scoffed.

"That does not make it less true, Lady Brienne," she countered, a smile flickering when she saw the look of disgust pass over Brienne's face.

Jaime snorted in amusement, raising his hand in a placating gesture as his eyes started to dance in the firelight. "How about we resort to given names? We are, after all, joining to eradicate two houses. I feel we are beyond formalities at this point in time."

Elyria's eyes flashed as the smile spread over her face. "You will join me, Jaime?" She asked with excitement.

He gave her a wry grin in response, reaching his hand out to shake hers over the table. "Where do we start?"

Two days later, Brienne regarded with disdain the farmers, sellswords, and hunters gathered in the full tavern before them. "And you're certain it is these men you wish to lead to defeat the Frey's and Bolton's, who have actual knights and warriors?"

Jaime smiled wryly, nodding along with Elyria as he heard the angry discussions of the bastard Bolton and the tightfisted treatment some had received from Lord Frey. "Aye," Jaime flashed a grin, "I think they are exactly the sort of men we need."

"And how will you know? Can they even fight? Would they?"

Elyria stepped forward, pushing fully back the hood of her cloak and drawing the eyes of all men in the room, men who she'd toiled beside and struggled with for most of her life in the swamps and bogs of the rivers. Several called out to greet her, eyeing with distrust her two companions, as she stepped up to stand before them in front of the hearth. Accepting a tankard of ale, Elyria nodded and smiled at the rapt attention the farmers and warriors alike paid her. "Gentleman!" She called out, voice ringing through the room as Jaime and Brienne watched from the door. Roars and cheery replies greeted her as she took a large swig of her ale.

"You have watched me grow from a babe to a woman, sheltering me and shuffling me about the marshes, keeping my late mother and father's secret as if it were your own. You have welcomed me in your homes; you have welcomed me in your towns; you have welcomed me in your rivers and farmlands. You have saved my life more times than I may count, with more sacrifices than I may repay in a lifetime." She raised her arm, gesturing widely across the room, as her gaze slowly met each in turn. "Walder Frey of The Twins and Roose Bolton of the Dreadfort wish to overthrow House Stark, and claim your farms and women and children and swords, and likely your very lives, as their own." A chorus of boos echoed through the tavern, loud enough to rattle the floorboards upon which they stood.

Elyria waved her arm, holding a hand up to silence them. "It is time I return the favor, gentleman. It is time I took a stand. It is time we stand together, to fight for our women, to fight for our freedom. It is time we showed the old lords of the great houses that we take no King but our own. And it is time, sirs, that Westeros were free from corrupt overlords who maintain no interests but their own, squeezing their people dry as they live lives of luxury, benefiting from wars they never fought for, never bled for, never sacrificed for."

The men bellowed and cheered, standing to rattle the earth as one as they roared with indignation and pride. "It is time we stand and fight, gentleman," Elyria's clear voice carried over the shouts as a hush fell on the crowd. "Are you with me?"

The screams and war cries echoed out of the tavern and into the night, as one by one men kneeled before Elyria, pledging fealty as she gathered an army of common folk and men who'd long since been neglected, discarded, or forgotten.

In the corner of the tavern, Brienne's amused gaze met Jaime's as they watched man after man enlist their help, hundreds lining up outside the door. "That was quite a speech," she said dryly, flushing as Jaime's laughter rang out beside her.

"It was, indeed! It seems the little Ice Queen may lead us to victory yet," he chuckled with amusement.

"They will raise her up higher than the Starks, when this is done," Brienne warned, narrowing her eyes as she noted the devotion on the faces spread out before her.

Jaime nodded in agreement, a wry smile playing on his face. "Wouldn't that be interesting? A battle for the throne between the Ice Queen and the Wolf King?" He quirked a brow in amusement as he nodded towards Elyria. "How on earth would we decide which side we were on, Brienne?"

Brienne flushed at his use of "we" and shook her head. "I will follow you wherever you lead us, my lord."

Jaime chuckled with amusement, raising his tankard of ale to his lips. "One war at a time Brienne," he mused, taking a long draft. "One war at a time," he repeated to himself softly.


	5. Chapter 5

**This is a shorter chapter, but I felt it was necessary. I hope you enjoy! THANK YOU to everyone commenting on and following this story! :)**

Robb Stark felt positively murderous.

Standing in his tent while his mother smugly laid the evidence before him, he could help but flush red in shame. His lady wife, his _Queen_ , was a fucking _traitor._ A _whore._

Talisa had lured him in from the very moment she set foot in camp, treating Starks and Lannisters alike, fluttering her eyelashes at him, shooting him coy smiles. And he, like the fool Tywin Lannister just proved him to be, fell for it in a colossal error of judgment that would haunt him until his dying breath.

The Lannister squires attempting to sneak on foot into The Twins hadn't expected the Blackfish himself to be patrolling that night, mind too heavy with thoughts of battle to lull to sleep. Robb had the distinct impression he would thank the gods until his dying day for that coincidence. Only his great uncle would catch the shadows creeping through the night towards the keep; and catch them, he did.

The missives were hidden quite well on their person, but were eventually extracted and made plain, their truths spreading through the camp like wildfire, forcing Robb to bend to his mother and sentence to death his own Queen.

Talisa had confessed the truth of it before the first press of his blade. She was a ward of the Lannister's, sent by Lord Tywin himself to distract Robb, slip into his bed, learn his secrets, and put a knife through his heart before she was through.

And now, Lady Stark was practically gloating. Her cheeks were flushed, eyes bright, as she called for his Queen's head on a spike.

Lords Bolton and Umber alike nodded in agreement; his own Uncle Edmure stepping to unsheathe his broadsword Ice, and with his heart in his throat, Robb reached out to grasp the heavy sword and yield the justice he so desperately wished to avoid, but which his _wife_ so desperately deserved.

With barely a grunt of effort, he watched as his Queen's head rolled onto the dirt of his tent at his feet. He turned on his heel, his face a stone mask, and nodded for Lord Bolton to collect the body. Her head was to be wrapped and delivered posthaste to Lord Tywin without delay.

With a rolling stomach and a stinging hard, Robb bowed his head in shame once he was finally alone once more. He had learned this lesson well, and with a strange twist knew he had Tywin Lannister to think for it.

And Robb Stark would not be making the same mistake again.

Three moon turns later, King Robb settled his great furs around his shoulders, feeling as though he were steeling himself for battle, rather than for his bride. With nothing short of glee, Lord Frey had delighted in his acceptance to honor their previous betrothal, and Robb found his cold heart no longer cared which ugly daughter the old lord found fit to saddle him with.

He would marry for duty; he would marry to secure the realm; and he would be glad of it. He had Tywin Lannister to thank for that.

As his lady mother entered his tent to collect him for the ceremony, he couldn't quite shake the grim feeling of dread settling in a pit in his stomach. The low growl from Grey Wind as he marched his host into the gates of The Twins did nothing to dissuade the notion, and as King Robb made his way to the hall to wed his Frey bride, he felt an icy chill roll up his spine and into the air around him.

Jaime, Brienne and Elyria surveyed the host from their perch in the woods with an impending sense of anxiety.

"I have to admit, I'm a little impressed the cub executed his own _wife_ for treason," Jaime drawled, his eyebrow raised in wry amusement, as they watched the host process in through the gates of the keep.

Brienne concurred, adding that perhaps he wasn't as foolish as Lord Tywin had assumed.

"Yes, Brienne, I quite agree," Jaime added. "He wouldn't have won every battle if he were a fool, and the uncovering of his wife's betrayal more demonstrated the opposite, in my opinion." Jaime chuckled as he thought of how his father's face must have pinched when he realized that in the end it was he who was made to look the fool.

Elyria sighed heavily as the gates slammed closed, the sound of heavy iron clanking echoing across the rivers to where their own host was camped. "Are the men ready, Jaime?"

He nodded, his spine straightening as the anticipation of battle made his heart start to race and his blood start to heat. "They are, Ice Queen," he confirmed in that dry humor of his, and Brienne barely contained the roll of her eyes.

The frosty glare Elyria shot in his direction actually made a chill run through him, and he thought not for the first time that the moniker was not that far from the truth.

"It is a miracle no word of us has reached the Frey's," Brienne commented, turning to follow her comrades back down to the camp.

"These are my people, Brienne," Elyria said coldly. "They will not betray their own."

One look at the hard faces of the men and boys who had gathered to follow their lady to take The Twins, and Brienne had no doubt that Elyria spoke truly. She was their lady, their Ice Queen, their savior sent down from the gods to rid them of those who would do them harm.

And tonight, when darkness had fallen, she would reclaim their homes.

Elyria led her army to the banks of the river, the light of the fires inside the keep sparkling across the water. Though Jaime and Brienne eyed her dubiously, her men had no doubt.

"Gods grant my body strength and my soul ice as I deliver death this night," their lady whispered, breath on the breeze heading into the night.

The Kingslayer's eyes widened to the point of fear at the sight before him, the crackling confirming what he refused to believe.

Before their host, the rivers themselves turned to a sheet of ice, waves and ripples frozen in their ascent, creating a silent path forward for them to march on the keep, undetected by the guards on the bridge and the walls this night.

Footfalls silenced by the icy crust below them, Elyria glided forward, leading her army to the gates of Walder Frey.


	6. Chapter 6

**OK you guys, I've tinkered with this chapter repeatedly and *fingers crossed* finally think I've got it right. THANK YOU to everyone supporting this story! I know I'm taking a lot of creative licenses here, and I really appreciate your kudos, comments, and general encouragement.**

 **PLEASE let me know what you think of this chapter! :D Enjoy!**

They broke through the main drawbridge without a moment to spare, frost seeping into the stone and freezing slowly upwards like tendrils on a vine, causing the wood to warp as they broke their way through. The sight that greeted them made nausea roil in all who were present, sickened as they were by the beginnings of a slaughter. Bolton and Frey men were murdering Robb Stark's army in their beds, while the doors into the keep had been sealed shut.

Elyria's army fanned out, silent in step, swift and sure in purpose, as they crept out to meet Frey and Bolton in battle, quickly uniting the remaining Stark warriors as they retook the ground they had lost and laid waste to what was left behind them. "Let no man who betrayed the Starks survive this night," Elyria called quietly to the leader of the guard, who nodded in agreement before slipping off through the fog that had begun to roll in from the river.

Heavily cloaked in furs, Elyria, Jaime and Brienne led their own raiding party up the very walls of the keep and down the ramparts, stealthily creeping towards the great hall and the screams and cries within. Throats were sliced and the keep was bathed in blood before any man, be he Bolton or Frey, could raise the alarm that a second army had joined them this night.

With a second prayer thrown up to the gods, Elyria settled her shoulders and drew out her knives. She hoped she was not too late.

The first bolt from the upper landing missed its intended target, and instead sunk into Roslin Frey's skull directly between her eyes. With a roar, Robb charged towards his mother, while his eyes frantically searched for any friendly men at arms. Men rained arrows down into the center of the hall while others rushed in to fight his unarmed lords. As the dirt thickened into mud with blood, he felt a wild fear creep into his eyes.

Up on his dirt caked throne, Lord Walder Frey nearly cackled with glee.

"Lord Bolton!" Robb called, eyes alighting, finally, upon a friendly face.

Across the hall, Lady Catelyn's eyes were blown wide with fear, and in desperation she frantically took hold of the hair of Lord Frey's bride, yanking her from under the Lord's table and up to stand before her, knife pricking a red line into her slim throat. "Stop this madness!" Catelyn screamed, tears streaming down her face as she watched Lord Bolton make his way towards her son, a dagger drawn and held against his right thigh.

"Your Grace," Lord Bolton said silkily, eyes laden with malice and a cold smile gracing his lips as he came to rest before his King. "The Lannister's send their regards."

Robb's eyes flew wide in shock as he felt the dagger pierce his side, before everything faded it black.

"Indeed they do, my Lord," Ser Jaime called drily, eyes rolling with amusement as he saw Lord Bolton's hand fall away from Robb Stark, the dagger he had gripped clattering to the blood soaked floor beneath him.

As Lord Bolton stared in shock at Elyria's dagger thrumming happily through the palm of his hand, Brienne threw open the doors of the hall to welcome in Elyria's soldiers. Catelyn dropped Walder Frey's bride to the floor as she collapsed at the side of her son, pressing her hands to his doublet to stem the flow of blood. With a thousand prayers to the gods, Catelyn realized that the wound was merely an inch deep, and seemed to miss anything vital. Tears rolled down her face as she watched her son sleepily blink open his eyes, taking in her face before widening in alarm as he jerked upright to survey the hall.

"Secure the keep!" Ser Jaime commanded their men, turning back towards the high table at the feel of the chill heavy in the air.

For there she stood, as rivulets of ice seeped into the stone and chilled the air to the core. The Ice Queen, in all her frozen glory.

Elyria's hand was fisted through the greasy locks of Walder Frey, her eyes glinting steel as she yanked him roughly out of his chair, around the dias and down to kneel before the hall. Jaime kicked Lord Bolton forward, grabbing a fistful of his doublet and shoving him down to kneel beside his host.

"My lords," he drawled, green eyes glittering fiercely in the firelight. "We thank you for your hospitality."

"What do you want," Lord Frey called out, hoarse voice grating over the din of battle as he struggled against Elyria's hold in his thinning hair.

"To deliver a message, my lord." Elyria's smooth voice sent a chill down each spine in the room, and the strength in her tone left no doubt as to who was victorious this night.

"Well, be on with it then, you stupid girl," he replied with false bravado, unable to hide the sight and stench of the urine beginning to stain his breeches.

Her smile would haunt her foes to the end of their days as they looked on while she slipped her dagger down to tickle along Lord Frey's throat. Her eyes locking on King Robb's from across the room, the ferocity in them made his blood run cold while her hands held firm. "Winter is here," she whispered, slipping the blade below his skin to slit his throat.

Lord Bolton jerked as the blood spewed out of Walder Frey's throat and coated the dirt floor on which they knelt. "My lady, I-"

"Spare him," King Robb called out as he pushed his way up to stand, supported by the Greatjon and his mother.

Elyria's eyes narrowed and Jaime looked on in amusement at what would become perhaps the first of many scuffles between this now infamous pair of regents. "I beg pardon, Your Grace?" Her voice was so soft, so smooth, yet it was impossible to miss the shards of glass aimed at his direction in her response.

"Death is too kind a punishment for Lord Bolton, my lady," King Robb replied, the strength of the wolf in his voice and the light of the fire in his eyes as he took in the blood soaked woman who'd saved the North this night.

With a graceful incline of her head, Elyria released her hold on Lord Bolton's collar and re-sheathed her dagger at her side. "As you say, Your Grace."

With a cry of delight, Lady Catelyn embraced Brienne, smiling on her fondly as she then turned to greet Ser Jaime. "I am surprised to see you here when it seems your own father was behind this plot, Ser," she said, venom thick and heavy in her shaken voice.

Jaime's eyes narrowed as he turned to study Lord Bolton, kneeling on the floor. "The chance for vengeance was too strong to resist, my lady." He smiled lazy as he turned back around, glancing in Elyria's direction. "Besides, who could resist that fair maiden and her directives from the gods?"

As Elyria made her way to stand before the King of the North, Robb couldn't help but stare. She was beautiful, thick black locks tumbling out of her braid to ring her porcelain skin, speckled with droplets of blood that glittered like gold. Her eyes were cold but round as a doe's, a tantalizing combination of innocence and warrior making his blood run hot at thoughts of what might lie beneath her heavy cloak of furs.

"To whom do we owe the North, my lady?" He asked softly, shrewd eyes never leaving hers. His breath caught at the slight smile that graced her face when Ser Jaime answered in response.

"Don't you recognize her, King Robb? Don't you feel the chill in the air? Can't you see the ice on the stone pavers?" Jaime's broad voice was thick with amusement and his grin was wide as he gestured with his good hand around the hall.

Brienne rolled her eyes to Lady Catelyn before smiling and nodding toward Elyria.

Robb's brow creased in thought and his eyes narrowed sharply as they wandered once more over the slim frame before him. "It couldn't be," he said in bewilderment, turning a questioning glance towards the Greatjon.

The great man's own brow creased in confusion in response, and he shrugged his massive shoulders before turning his attention back to Ser Jaime.

"My lords, my ladies, my King. It is, quite sincerely, my honor to present to you, Elyria Baratheon, only daughter of Robert Baratheon and Minerva Tully, first daughter of Lord Hoster Tully from his first marriage, half-sister to Catelyn, Lysa and Edmure, who died in childbirth at the birth of their only babe." Catelyn's mouth dropped open as she stared at Elyria, and the other lords shifted in confusion, glancing between their King and his mother for some confirmation that this story could be true.

"Young Wolf, King of the North. Meet, the Ice Queen," Jaime's smile was wider than a lion's and he licked his lips like the cat who got the cream as he watched the hall erupt into chaos around him.


	7. Chapter 7

**I hope you enjoy this update! :) Drop a comment and let me know what you think!**

They convened the war council in Walder Frey's solar, Lord Bolton for the time being held in chains in the dungeons of the Twins. King Robb gathered his most trusted advisors, including the Lords Greatjon and Smalljon Umber, the Blackfish, and his lady mother Lady Stark.

Elyria fought to contain her smile at the look of disdain the Greatjon shot her chosen advisors, Ser Jaime and Brienne. With a flippant shrug, she raised her eyebrow in challenge, daring those in attendance to question her allies or her decisions. Lady Stark rose to the challenge, clearing her throat delicately. "The Kingslayer is your trusted advisor, Elyria?"

"My lady, you should address my Queen properly if you wish to garner her support," Jaime retorted with a twinkle in his eye, as Brienne shifted uncomfortably between her current and former mistresses.

The Greatjon scoffed, his booming voice echoing throughout the small chamber. "And what need have we for the peasant Queen's support, I ask you?"

"She is Robert Baratheon's rightful heir from his first marriage, Lord Umber," the Blackfish, Lord Brynden Tully, intoned respectfully. "And the lady deserves to be treated as such."

Elyria was locked in a heated stare with the wolf King, his eyes boring into hers as their bannermen battled with words around them. Lady Stark took hold of Elyria's arm, breaking her reverie and snapping her gaze back. "It is truly you, isn't it?" She whispered softly, tears creeping into the corners of her eyes in recognition.

Elyria gave her a small half smile, her lips curling upward as she gracefully inclined her head. "It is, my lady. And to whom it may concern, the peasants I am Queen of just saved your very lives, so I expect you will accord them the respect they are do." Her words brought a chill to the room level with the ice in her eyes, and the Greatjon had the capacity to look appropriately shamed as he bowed his head and shifted his weight from foot to foot.

"So we are, my lady, I assure you," King Robb said smoothly, his gaze never once wavering in its study of her countenance, his eyes still continuing to roam her face.

"I think the most important question is, how do we move forward? We have one who is King of the Lords, the other who is Queen of the vassals and those who work the lands," the Blackfish's smooth words brought Elyria's gaze flickering upwards as she heard Ser Jaime shift his stance behind her.

"Isn't it obvious, my lord?"

The Greatjon narrowed his eyes as he looked in turn at the faces in the room before shaking his head. "Is it another war we're having? We cannot defeat the Lannister's if we are too busy defeating ourselves."

Ser Jaime scoffed and rolled his eyes, a lazy smile filled with disdain alighting his handsome face. "I had not expected you to understand, Greatjon, but surely the other _advisors_ of King Robb see the… unique, solution which now presents itself."

"No, Jaime," Elyria said sharply, her eyes widening a fraction before narrowing at the sly smirk spreading over his face.

"Come now, my lady, surely it wouldn't be so bad as all that," he replied, green eyes glittering at her discomfort while his smirk spread wider and his white teeth shown in the firelight.

"It would nearly double your forces, Robb," Lady Stark agreed, a small smile on her face. "You would have the army you needed to take the Rock and defeat Tywin Lannister once and for all."

"I fail to comprehend why the younger lion would have interest in marching on the old, for any purpose other than treason or deceit," the Blackfish's eyes narrowed in accusation as he studied the face of the Kingslayer.

"I have no intention of marching on the Rock," Elyria said coldly, her pale eyes glancing in warning towards Ser Jaime before returning back to the young wolf.

"Then what, my lady, are your intentions?" His voice was smoother than silk, a gentle caress, and Elyria had to blink several times before the cold demeanor she wore like a mantle was once more firmly wrapped around her shoulders.

"To march on the wall."

The older men scoffed, and Robb shared a smile with the Blackfish before his eyes widened in startled alarm when he took in the serious gazes and raised eyebrows of Elyria, Brienne and Ser Jaime. "You're serious," he deadpanned, disbelief coloring his face.

"You wish to take the wall?" The Greatjon's laughter shook the wooden table they were seated around as he rumbled in amusement.

"Not exactly," Ser Jaime replied, glancing pointedly at Elyria and nodding his head towards King Robb's council.

"I spoke with the gods, and they commanded that I march my host North to the wall and beyond, to defeat the whitewalkers."

"The gods told you to defeat the whitewalkers." The Greatjon stared as if she had two heads, his eyes blown wide and his brow creased in a frown.

"Well, a messenger from the gods," she granted, serious eyes surveying the looks of disbelief before her.

"And who, my lady, was this messenger?" King Robb's mouth twitched as he raised his brow in question, until her next words wiped the smirk off his face in an instant.

"His name was Bran," she whispered softly, swallowing as the room stilled into silence, frozen in shock as Lady Stark clutched her arm with grief.

"What do you mean, you've seen Bran? My son? You've spoken with him? Is this some cruel joke?" Her grief was choking, sucking the air out of the room as she clawed into Elyria's arm, while the men watched her with a mixture of suspicion and uneasy hope.

Elyria turned fully, taking Lady Stark's hands in her own and gentling her voice as she recounted her dream. She finished with "he told me to eliminate Walder Frey, secure the Twins, unite the North and defeat the whitewalkers, my lady. He is alive, and he is beyond the wall, watching through the heart trees in the godswoods. I would swear it."

As a hushed silence fell about the room and Lady Stark began to weep and give thanks, Ser Jaime turned his sly smile once more to the lords of the North before him. "So when is the wedding?"

Elyria choked on the sip of wine she'd taken, turning in disbelief and shaking her head with disapproval. "I believe this shows we don't need-"

"Pardons, my lady," King Robb interrupted smoothly, the hint of a smile dancing across his bearded face, "but if we were decreed from the gods to unite the North, and marriage would most certainly accomplish this directive, who are we to refuse?"

Elyria's face paled as his eyes began to shimmer with laughter, and Ser Jaime all but cackled in amusement. "Fetch a Septon at first light, Lord Umber! On the morrow, we unite the North into one kingdom, and on the next, we march for the wall."

Elyria found herself the next evening dressed in a silk gown of shimmering silver, white lace patterns decorating the bodice and sleeves, and she wondered once more to Brienne why this was truly necessary.

"You know it is, my Queen," she replied, a faint glimmer of amusement dancing in her eyes as Elyria continued her unladylike grumbling while she fidgeted with the material before the mirror in her chambers. Catching the end of something sounding suspiciously like 'see if I don't marry you off when you're least expecting it', Brienne had to stifle the laughter beginning to chortle out of her.

Elyria glanced up at her through the mirror and a wide smile cracked her face, the first warmth thawing in those pale eyes that Brienne had seen since they'd marched on the Twins. A knock sounded twice on the door before Ser Jaime strode brusquely in, carrying his white Kingsguard cloak as he sauntered up to stand behind Elyria before the mirror.

"Are you ready, my Queen?" Brienne asked softly, fighting to hide another smile as she saw Elyria swallow and nod as if she were heading once more to freeze the Twins in the middle of the night, her cold face drawn so fiercely she was certain King Robb would search frantically for the assassin lying in wait.

"Not yet!" Jaime said loudly, before stepping wide and sweeping the white cloak over Elyria's shoulders. As she began to stutter a protest, he held up a finger, eyes twinkling as he shook his head. "Now now, my Queen. We cannot marry you off without a maiden's cloak, can we? It wouldn't be proper! So I was thinking, in the absence of a cloak of your house, perhaps a virginal white cloak would do the trick?"

His smile was wolfish as she shot him a murderous glare, growling low in her throat before tilting her head up high, the mask of the Queen sliding over her pretty face. "I am ready," she said loftily, holding her arm for Ser Jaime to escort her.

His smile slipped down into a fonder, gentler one as he brushed an errant curl back from her face, tucking it behind her ear. "Yes, my Queen, I do believe you are," he said softly, before taking her arm and leading her out to the woods to meet the Septon, Brienne following softly in their wake.

 **Up next: the wedding and the bedding, with sexy time ensuing** **J**


End file.
